package com.leecode.xiehf.page_01;

/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * <p>
 * https://leetcode-cn.com/problems/trapping-rain-water/
 */
public class Solution_0042 {

    public static void main(String[] args) {
        Solution_0042 solution = new Solution_0042();
        int result = solution.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
//        int result = solution.trap(new int[]{2, 0, 2});
        System.out.println(result);
    }


    public int trap(int[] height) {
        int len = height.length;
        if (len <= 2) {
            return 0;
        }
        // 从左到右
        int bottom = 0;
        int total = 0;
        int preIndex = 0;
        for (int i = 1; i < len; i++) {
            if (height[i] >= height[preIndex]) {
                // 形成了池子
                total += (i - preIndex - 1) * height[preIndex] - bottom;
                bottom = 0;
                preIndex = i;
            } else {
                bottom += height[i];
            }
        }
        bottom = 0;
        preIndex = len - 1;
        for (int j = len - 2; j >= 0; j--) {
            if (height[j] > height[preIndex]) {
                // 形成了池子
                total += (preIndex - j - 1) * height[preIndex] - bottom;
                bottom = 0;
                preIndex = j;
            } else {
                bottom += height[j];
            }
        }
        return total;
    }
}
